package pers.qianyu.month_202101.date_20210128;

import pers.qianyu.util.*;
import pers.qianyu.util.model.*;

/**
 * 剑指 Offer 37. 序列化二叉树
 * https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
 * - 递归方式
 *
 * @author mizzle rain
 * @date 2021年1月28日21:13:50
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        return recur_s(root);
    }

    private String recur_s(TreeNode root) {
        if (root == null) return "#";
        String left = recur_s(root.left);
        String right = recur_s(root.right);
        return root.val + "," + left + "," + right;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.length() == 0) return null;
        String[] arr = data.split(",");
        return recur_d(arr);
    }

    private int cur = 0;

    private TreeNode recur_d(String[] arr) {
        String s = arr[cur++];
        if (s.equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(s));
        root.left = recur_d(arr);
        root.right = recur_d(arr);
        return root;
    }

    public static void main(String[] args) {
        Codec codec = new Codec();
        TreeNode root = BinTreeUtil.generateBinTree(new Integer[]{1, 2, 3, null, null, 4, 5});
        String s = codec.serialize(root);
        System.out.println("s = " + s);
        TreeNode d = codec.deserialize(s);
        System.out.println(d);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));